package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * @version 1.0
 * @date 2021/11/14 21:37
 */
public class moveZeroes {

    public static void main(String[] args) {
        moveZeroes(new int[]{1, 0, 2, 3, 0, 8});
    }

    // 双指针，i 和 j 表示初始下标 0。
    // 思想是 把非0 元素依次移到数组左边，然后把数组后面的元素变为0
    static void moveZeroes(int[] nums) {
        // 记录第一个0的所在位置
        int j = 0;
        // 左移非0 元素
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) nums[j++] = nums[i];
        }
        // 重置右边元素为0
        for (int i = j; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    // 双指针，遇到不等于0的元素
    static void moveZeroes1(int[] nums) {
        // 记录第一个0的所在位置，假设nums[0]是0，那么j就是0
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                // 假设下一个位置的数字为 0;
                j++;
            }
        }
    }

    /**
     * 二刷时的解法
     * @author Cheng Jun
     * @date 2022/7/15 11:10
     * @param nums
     * @return void
     */

    static void moveZeroes2(int[] nums) {
        int firstZero = -1;
        for(int i = 0; i < nums.length; i++){
            // 找第一个0出现的位置
            if(nums[i] == 0 && firstZero == -1){
                firstZero = i;
                continue;
            }
            // 找到后，并且当前nums[i]不是0，交换位置，
            if(firstZero >= 0 && nums[i] != 0){
                nums[firstZero] = nums[i];
                nums[i] = 0;
                firstZero++;
            }
        }
    }
}
